In modern retail transactions, predetermined price transactions are common, with market transactions, i.e., commerce conducted in a setting which allows the transaction price to float based on the respective valuation allocated by the buyer(s) and seller(s), often left to specialized fields. While interpersonal negotiation is often used to set a transfer price, this price is often different from a transfer price that might result from a best-efforts attempt at establishing a market price. Assuming that the market price is optimal, it is therefore assumed that alternatives are sub-optimal. Therefore, the establishment of a market price is desirable over simple negotiations.
One particular problem with market-based commerce is that both seller optimization and market efficiency depend on the fact that representative participants of a preselected class are invited to participate, and are able to promptly communicate, on a relevant timescale, in order to accurately value the goods or services and make an offer. Thus, in traditional market-based system, all participants are in the same room, or connected by a high quality (low latency, low error) telecommunications link. Alternately, the market valuation process is prolonged over an extended period, allowing non-real time communications of market information and bids. Thus, attempts at ascertaining a market price for non-commodity goods can be subject to substantial inefficiencies, which reduce any potential gains by market pricing. Further, while market pricing might be considered “fair”, it also imposes an element of risk, reducing the ability of parties to predict future pricing and revenues. Addressing this risk may also improve efficiency of a market-based system, that is, increase the overall surplus in the market.
When a single party seeks to sell goods to the highest valued purchaser(s), to establish a market price, the rules of conduct typically define an auction. Typically, known auctions provide an ascending price or descending price over time, with bidders making offers or ceasing to make offers, in the descending price or ascending price models, respectively, to define the market price. After determining the winner of the auction, typically a bidder who establishes a largest economic surplus, the pricing rules define the payment, which may be in accordance with a uniform price auction, wherein all successful bidders pay the lowest successful bid, a second price auction wherein the winning bidder pays the amount bid by the next highest bidder, and pay-what-you-bid (first price) auctions. The pay-what-you-bid auction is also known as a discriminative auction while the uniform price auction is known as a non-discriminative auction. In a second-price auction, also known as a Vickrey auction, the policy seeks to create a disincentive for speculation and to encourage bidders to submit bids reflecting their true value for the good, rather than “shaving” the bid to achieve a lower cost. In the uniform price and second price schemes, the bidder is encourages to disclose the actual private value to the bidder of the good or service, since at any price below this amount, there is an excess gain to the buyer, whereas by withholding this amount the bid may be unsuccessful, resulting in a loss of the presumably desirable opportunity. In the pay-what-you-bid auction, on the other hand, the buyer need not disclose the maximum private valuation, and those bidders with lower risk tolerance will bid higher prices. See, ww.isoc.org/inet98/proceedings/3b/3b—3.html; www.ibm.com/iac/reports-technical/reports-bus-neg-internet.html.
Two common types of auction are the English auction, which sells a single good to the highest bidder in an ascending price auction, and the Dutch auction, in which multiple units are available for sale, and in which a starting price is selected by the auctioneer, which is successively reduced, until the supply is exhausted by bidders (or the minimum price/final time is reached), with the buyer(s) paying the lowest successful bid. The term Dutch auction is also applied to a type of sealed bid auction. In a multi-unit live Dutch auction, each participant is provided with the current price, the quantity on hand and the time remaining in the auction. This type of auction, typically takes place over a very short period of time and there is a flurry of activity in the last portion of the auction process. The actual auction terminates when there is no more product to be sold or the time period expires.
In selecting the optimal type of auction, a number of factors are considered. In order to sell large quantities of a perishable commodity in a short period of time, the descending price auctions are often preferred. For example, the produce and flower markets in Holland routinely use the Dutch auction (hence the derivation of the name), while the U.S. Government uses this form to sell its financial instruments. The format of a traditional Dutch auction encourages early bidders to bid up to their “private value”, hoping to pay some price below the “private value”. In making a bid, the “private value” becomes known, helping to establish a published market value and demand curve for the goods, thus allowing both buyers and sellers to define strategies for future auctions.
In an auction, typically a seller retains an auctioneer to conduct an auction with multiple buyers. (In a reverse auction, a buyer solicits the lowest price from multiple competing vendors for a desired purchase). Since the seller retains the auctioneer, the seller essentially defines the rules of the auction. These rules are typically defined to maximize the revenues or profit to the seller, while providing an inviting forum to encourage a maximum number of high valued buyers. If the rules discourage high valuations of the goods or services, or discourage participation by an important set of potential bidders, then the rules are not optimum. Rules may also be imposed to discourage bidders who are unlikely to submit winning bids from consuming resources. A rule may also be imposed to account for the valuation of the good or service applied by the seller, in the form of a reserve price. It is noted that these rules typically seek to allocate to the seller a portion of the economic benefit that would normally inure to the buyer (in a perfectly efficient auction), creating an economic inefficiency. However, since the auction is to benefit the seller, not society as a whole, this potential inefficiency is tolerated. An optimum auction thus seeks to produce a maximum profit (or net revenues) for the seller. An efficient auction, on the other hand, maximizes the sum of he utilities for the buyer and seller. It remains a subject of academic debate as to which auction rules are most optimum in given circumstances; however, in practice, simplicity of implementation may be a paramount concern, and simple auctions may result in highest revenues; complex auctions, while theoretically more optimal, may discourage bidders from participating or from applying their true and full private valuation in the auction process.
Typically, the rules of the auction are predefined and invariant. Further, for a number of reasons, auctions typically apply the same rules to all bidders, even though, with a priori knowledge of the private values assigned by each bidder to the goods, or a prediction of the private value, an optimization rule may be applied to extract the full value assigned by each bidder, while selling above the seller's reserve.
In a known ascending price auction, each participant must be made aware of the status of the auction, e.g., open, closed, and the contemporaneous price. A bid is indicated by the identification of the bidder at the contemporaneous price, or occasionally at any price above the minimum bid increment plus the previous price. The bids are asynchronous, and therefore each bidder must be immediately informed of the particulars of each bid by other bidders.
In a known descending price auction, the process traditionally entails a common clock, which corresponds to a decrementing price at each decrement interval, with an ending time (and price). Therefore, once each participant is made aware of the auction parameters, e.g., starting price, price decrement, ending price/time, before the start of the auction, the only information that must be transmitted is auction status (e.g., inventory remaining).
As stated above, an auction is traditionally considered an efficient manner of liquidating goods at a market price. The theory of an auction is that either the buyer will not resell, and thus has an internal or private valuation of the goods regardless of other's perceived values, or that the winner will resell, either to gain economic efficiency or as a part of the buyer's regular business. In the later case, it is a general presumption that the resale buyers are not in attendance at the auction or are otherwise precluded from bidding, and therefore that, after the auction, there will remain demand for the goods at a price in excess of the price paid during the auction. Extinction of this residual demand results in the so-called “winner's curse”, in which the buyer can make no profit from the transaction during the auction. Since this detracts from the value of the auction as a means of conducting profitable commerce, it is of concern to both buyer and seller.
Research into auction theory (game theory) shows that in an auction, the goal of the seller is to optimize the auction by allocating the goods inefficiently, if possible, and thus to appropriate to himself an excess gain. This inefficiency manifests itself by either withholding goods from the market or placing the goods in the wrong hands. In order to assure for the seller a maximum gain from a misallocation of the goods, restrictions on resale are imposed; otherwise, post auction trading will tend to undue the misallocation, and the anticipation of this trading will tend to control the auction pricing. The misallocations of goods imposed by the seller through restrictions allow the seller to achieve greater revenues than if free resale were permitted. It is believed that in an auction followed by perfect resale, that any mis-assignment of the goods lowers the seller's revenues below the optimum and likewise, in an auction market followed by perfect resale, it is optimal for the seller to allocate the goods to those with the highest value. Therefore, if post-auction trading is permitted, the seller will not benefit from these later gains, and the seller will obtain sub optimal revenues.
These studies, however, typically do not consider transaction costs and internal inefficiencies of the resellers, as well as the possibility of multiple classes of purchasers, or even multiple channels of distribution, which may be subject to varying controls or restrictions, and thus in a real market, such theoretical optimal allocation is unlikely. In fact, in real markets the transaction costs involved in transfer of ownership are often critical in determining a method of sale and distribution of goods. For example, it is the efficiency of sale that motivates the auction in the first place. Yet, the auction process itself may consume a substantial margin, for example 1-15% of the transaction value. To presume, even without externally imposed restrictions on resale, that all of the efficiencies of the market may be extracted by free reallocation, ignores that the motivation of the buyer is a profitable transaction, and the buyer may have fixed and variable costs on the order of magnitude of the margin. Thus, there are substantial opportunities for the seller to gain enhanced revenues by defining rules of the auction, strategically allocating inventory amount and setting reserve pricing.
Therefore, perfect resale is but a fiction created in auction (game) theory. Given this deviation from the ideal presumptions, auction theory may be interpreted to provide the seller with a motivation to misallocate or withhold based on the deviation of practice from theory, likely based on the respective transaction costs, seller's utility of the goods, and other factors not considered by the simple analyses.
In many instances, psychology plays an important role in the conduct of the auction. In a live auction, bidders can see each other, and judge the tempo of the auction. In addition, multiple auctions are often conducted sequentially, so that each bidder can begin to understand the other bidder's patterns, including hesitation, bluffing, facial gestures or mannerisms. Thus, bidders often prefer live auctions to remote or automated auctions if the bidding is to be conducted strategically.
Internet auctions are quite different from live auctions with respect to psychological factors. Live auctions are often monitored closely by bidders, who strategically make bids, based not only on the “value” of the goods, but also on an assessment of the competition, timing, psychology, and progress of the auction. It is for this reason that so-called proxy bidding, wherein the bidder creates a preprogrammed “strategy”, usually limited to a maximum price, are disfavored as a means to minimize purchase price, and offered as a service by auctioneers who stand to make a profit based on the transaction price. A maximum price proxy bidding system is somewhat inefficient, in that other bidders may test the proxy, seeking to increase the bid price, without actually intending to purchase, or contrarily, after testing the proxy, a bidder might give up, even below a price he might have been willing to pay. Thus, the proxy imposes inefficiency in the system that effectively increases the transaction cost.
In order to address a flurry of activity that often occurs at the end of an auction, an auction may be held open until no further bids are cleared for a period of time, even if advertised to end at a certain time. This is common to both live and automated auctions. However, this lack of determinism may upset coordinated schedules, thus impairing efficient business use of the auction system.
Game Theory
Use of Game Theory to control arbitration of ad hoc networks is well known. F. P. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49, 1998. citeseer.ist.psu.edu/kelly98rate.html; J. MacKie-Mason and H. Varian. Pricing congestible network resources. IEEE Journal on Selected Areas in Communications, 13(7):1141-1149, 1995. Some prior studies have focused on the incremental cost to each node for participation in the network, without addressing the opportunity cost of a node foregoing control over the communication medium. Courcoubetis, C., Siris, V. A. and Stamoulis, G. D. Integration of pricing and flow control for available bit rate services in ATM networks. In Proceedings IEEE Globecom '96, pp. 644-648. London, UK. citeseer.ist.psu.edu/courcoubetis96integration.html.
A game theoretic approach addresses the situation where the operation of an agent which has freedom of choice, allowing optimization on a high level, considering the possibility of alternatives to a well designed system. According to game theory, the best way to ensure that a system retains compliant agents is to provide the greatest anticipated benefit, at the least anticipated cost, compared to the alternates.
Game Theory provides a basis for understanding the actions of Ad hoc network nodes. A multihop ad hoc network requires a communication to be passed through a disinterested node. The disinterested node incurs some cost, thus leading to a disincentive to cooperate. Meanwhile, bystander nodes must defer their own communications in order to avoid interference, especially in highly loaded networks. By understanding the decision analysis of the various nodes in a network, it is possible to optimize a system which, in accordance with game theory, provides benefits or incentives, to promote network reliability and stability. The incentive, in economic form, may be charged to those benefiting from the communication, and is preferably related to the value of the benefit received. The proposed network optimization scheme employs a modified combinatorial (VCG) auction, which optimally compensates those involved in the communication, with the benefiting party paying the second highest bid price (second price). The surplus between the second price and VCG price is distributed among those who defer to the winning bidder according to respective bid value. Equilibrium usage and headroom may be influenced by deviating from a zero-sum condition. The mechanism seeks to define fairness in terms of market value, providing probable participation benefit for all nodes, leading to network stability.
An ad hoc network is a wireless network which does not require fixed infrastructure or centralized control. The terminals in the network cooperate and communicate with each other, in a self organizing network. In a multihop network, communications can extend beyond the scope of a single node, employing neighboring nodes to forward messages to their destination. In a mobile ad hoc network, constraints are not placed on the mobility of nodes, that is, they can relocate within a time scale which is short with respect to the communications, thus requiring consideration of dynamic changes in network architecture.
Ad hoc networks pose control issues with respect to contention, routing and information conveyance. There are typically tradeoffs involving equipment size, cost and complexity, protocol complexity, throughput efficiency, energy consumption, and “fairness” of access arbitration. Other factors may also come into play. L. Buttyan and J.-P. Hubaux. Rational exchange—a formal model based on game theory. In Proceedings of the 2nd International Workshop on Electronic Commerce (WELCOM), November 2001. citeseer.ist.psu.edu/an01rational.html; P. Michiardi and R. Molva. Game theoretic analysis of security in mobile ad hoc networks. Technical Report RR-02-070, Institut Eurécom, 2002; P. Michiardi and R. Molva. A game theoretical approach to evaluate cooperation enforcement mechanisms in mobile ad hoc networks. In Proceedings of WiOpt'03, March 2003; Michiardi, P., Molva, R.: Making greed work in mobile ad hoc networks. Technical report, Institut Eurecom (2002) citeseer.ist.psu.edu/michiardi02making.html; S. Shenker. Making greed work in networks: A game-theoretic analysis of switch service disciplines. IEEE/ACM Transactions on Networking, 3(6):819-831, December 1995; A. B. MacKenzie and S. B. Wicker. Selfish users in aloha: A game-theoretic approach. In Vehicular Technology Conference, 2001. VTC 2001 Fall. IEEE VTS 54th, volume 3, October 2001; J. Crowcroft, R. Gibbens, F. Kelly, and S. Östring. Modelling incentives for collaboration in mobile ad hoc networks. In Proceedings of WiOpt'03, 2003.
Game theory studies the interactions of multiple independent decision makers, each seeking to fulfill their own objectives. Game theory encompasses, for example, auction theory and strategic decision-making. By providing appropriate incentives, a group of independent actors may be persuaded, according to self-interest, to act toward the benefit of the group. That is, the selfish individual interests are aligned with the community interests. In this way, the community will be both efficient and the network of actors stable and predictable. Of course, any systems wherein the “incentives” impose too high a cost, themselves encourage circumvention. In this case, game theory also addresses this issue.
In computer networks, issues arise as the demand for communications bandwidth approaches the theoretical limit. Under such circumstances, the behavior of nodes will affect how close to the theoretical limit the system comes, and also which communications are permitted. The well known collision sense, multiple access (CSMA) protocol allows each node to request access to the network, essentially without cost or penalty, and regardless of the importance of the communication. While the protocol incurs relatively low overhead and may provide fully decentralized control, under congested network conditions, the system may exhibit instability, that is, a decline in throughput as demand increases, resulting in ever increasing demand on the system resources and decreasing throughput. Durga P. Satapathy and Jon M. Peha, Performance of Unlicensed Devices With a Spectrum Etiquette,” Proceedings of IEEE Globecom, November 1997, pp. 414-418. citeseer.ist.psu.edu/satapathy97performance.html. According to game theory, the deficit of the CSMA protocol is that it is a dominant strategy to be selfish and hog resources, regardless of the cost to society, resulting in “the tragedy of the commons.” Garrett Hardin. The Tragedy of the Commons. Science, 162:1243-1248, 1968. Alternate Location: dieoff.com/page95.htm.
In an ad hoc network used for conveying real-time information, as might be the case in a telematics system, there are potentially unlimited data communication requirements (e.g., video data), and network congestion is almost guaranteed. Therefore, using a CSMA protocol as the paradigm for basic information conveyance is destined for failure, unless there is a disincentive to network use. (In power constrained circumstances, this cost may itself provide such a disincentive). On the other hand, a system which provides more graceful degradation under high load, sensitivity to the importance of information to be communicated, and efficient utilization of the communications medium would appear more optimal.
One way to impose a cost which varies in dependence on the societal value of the good or service is to conduct an auction, which is a mechanism to determine the market value of the good or service, at least between the auction participants. Walsh, W. and M. Wellman (1998). A market protocol for decentralized task allocation, in “Proceedings of the Third International Conference on Multi-Agent Systems,” pp. 325-332, IEEE Computer Society Press, Los Alamitos. In an auction, the bidder seeks to bid the lowest value, up to a value less than or equal to his own private value (the actual value which the bidder appraises the good or service, and above which there is no surplus), that will win the auction. Since competitive bidders can minimize the gains of another bidder by exploiting knowledge of the private value attached to the good or service by the bidder, it is generally a dominant strategy for the bidder to attempt to keep its private value a secret, at least until the auction is concluded, thus yielding strategies that result in the largest potential gain. On the other hand, in certain situations, release or publication of the private value is a dominant strategy, and can result in substantial efficiency, that is, honesty in reporting the private value results in the maximum likelihood of prospective gain.